1   /*
2    * Copyright (C) 2007 The Guava Authors
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License");
5    * you may not use this file except in compliance with the License.
6    * You may obtain a copy of the License at
7    *
8    * http://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS,
12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   * See the License for the specific language governing permissions and
14   * limitations under the License.
15   */
16  
17  package com.google.common.collect;
18  
19  import static com.google.common.base.Preconditions.checkNotNull;
20  
21  import com.google.common.annotations.GwtCompatible;
22  import com.google.common.annotations.VisibleForTesting;
23  
24  import java.io.Serializable;
25  import java.util.Collection;
26  import java.util.Comparator;
27  import java.util.Iterator;
28  import java.util.List;
29  import java.util.ListIterator;
30  import java.util.Map;
31  import java.util.Map.Entry;
32  import java.util.Queue;
33  import java.util.RandomAccess;
34  import java.util.Set;
35  import java.util.SortedMap;
36  import java.util.SortedSet;
37  
38  import javax.annotation.Nullable;
39  
40  /**
41   * Synchronized collection views. The returned synchronized collection views are
42   * serializable if the backing collection and the mutex are serializable.
43   *
44   * <p>If {@code null} is passed as the {@code mutex} parameter to any of this
45   * class's top-level methods or inner class constructors, the created object
46   * uses itself as the synchronization mutex.
47   *
48   * <p>This class should be used by other collection classes only.
49   *
50   * @author Mike Bostock
51   * @author Jared Levy
52   */
53  @GwtCompatible(emulated = true)
54  final class Synchronized {
55    private Synchronized() {}
56  
57    static class SynchronizedObject implements Serializable {
58      final Object delegate;
59      final Object mutex;
60  
61      SynchronizedObject(Object delegate, @Nullable Object mutex) {
62        this.delegate = checkNotNull(delegate);
63        this.mutex = (mutex == null) ? this : mutex;
64      }
65  
66      Object delegate() {
67        return delegate;
68      }
69  
70      // No equals and hashCode; see ForwardingObject for details.
71  
72      @Override public String toString() {
73        synchronized (mutex) {
74          return delegate.toString();
75        }
76      }
77  
78      // Serialization invokes writeObject only when it's private.
79      // The SynchronizedObject subclasses don't need a writeObject method since
80      // they don't contain any non-transient member variables, while the
81      // following writeObject() handles the SynchronizedObject members.
82    }
83  
84    private static <E> Collection<E> collection(
85        Collection<E> collection, @Nullable Object mutex) {
86      return new SynchronizedCollection<E>(collection, mutex);
87    }
88  
89    @VisibleForTesting static class SynchronizedCollection<E>
90        extends SynchronizedObject implements Collection<E> {
91      private SynchronizedCollection(
92          Collection<E> delegate, @Nullable Object mutex) {
93        super(delegate, mutex);
94      }
95  
96      @SuppressWarnings("unchecked")
97      @Override Collection<E> delegate() {
98        return (Collection<E>) super.delegate();
99      }
100 
101     @Override
102     public boolean add(E e) {
103       synchronized (mutex) {
104         return delegate().add(e);
105       }
106     }
107 
108     @Override
109     public boolean addAll(Collection<? extends E> c) {
110       synchronized (mutex) {
111         return delegate().addAll(c);
112       }
113     }
114 
115     @Override
116     public void clear() {
117       synchronized (mutex) {
118         delegate().clear();
119       }
120     }
121 
122     @Override
123     public boolean contains(Object o) {
124       synchronized (mutex) {
125         return delegate().contains(o);
126       }
127     }
128 
129     @Override
130     public boolean containsAll(Collection<?> c) {
131       synchronized (mutex) {
132         return delegate().containsAll(c);
133       }
134     }
135 
136     @Override
137     public boolean isEmpty() {
138       synchronized (mutex) {
139         return delegate().isEmpty();
140       }
141     }
142 
143     @Override
144     public Iterator<E> iterator() {
145       return delegate().iterator(); // manually synchronized
146     }
147 
148     @Override
149     public boolean remove(Object o) {
150       synchronized (mutex) {
151         return delegate().remove(o);
152       }
153     }
154 
155     @Override
156     public boolean removeAll(Collection<?> c) {
157       synchronized (mutex) {
158         return delegate().removeAll(c);
159       }
160     }
161 
162     @Override
163     public boolean retainAll(Collection<?> c) {
164       synchronized (mutex) {
165         return delegate().retainAll(c);
166       }
167     }
168 
169     @Override
170     public int size() {
171       synchronized (mutex) {
172         return delegate().size();
173       }
174     }
175 
176     @Override
177     public Object[] toArray() {
178       synchronized (mutex) {
179         return delegate().toArray();
180       }
181     }
182 
183     @Override
184     public <T> T[] toArray(T[] a) {
185       synchronized (mutex) {
186         return delegate().toArray(a);
187       }
188     }
189 
190     private static final long serialVersionUID = 0;
191   }
192 
193   @VisibleForTesting static <E> Set<E> set(Set<E> set, @Nullable Object mutex) {
194     return new SynchronizedSet<E>(set, mutex);
195   }
196 
197   static class SynchronizedSet<E>
198       extends SynchronizedCollection<E> implements Set<E> {
199 
200     SynchronizedSet(Set<E> delegate, @Nullable Object mutex) {
201       super(delegate, mutex);
202     }
203 
204     @Override Set<E> delegate() {
205       return (Set<E>) super.delegate();
206     }
207 
208     @Override public boolean equals(Object o) {
209       if (o == this) {
210         return true;
211       }
212       synchronized (mutex) {
213         return delegate().equals(o);
214       }
215     }
216 
217     @Override public int hashCode() {
218       synchronized (mutex) {
219         return delegate().hashCode();
220       }
221     }
222 
223     private static final long serialVersionUID = 0;
224   }
225 
226   private static <E> SortedSet<E> sortedSet(
227       SortedSet<E> set, @Nullable Object mutex) {
228     return new SynchronizedSortedSet<E>(set, mutex);
229   }
230 
231   static class SynchronizedSortedSet<E> extends SynchronizedSet<E>
232       implements SortedSet<E> {
233     SynchronizedSortedSet(SortedSet<E> delegate, @Nullable Object mutex) {
234       super(delegate, mutex);
235     }
236 
237     @Override SortedSet<E> delegate() {
238       return (SortedSet<E>) super.delegate();
239     }
240 
241     @Override
242     public Comparator<? super E> comparator() {
243       synchronized (mutex) {
244         return delegate().comparator();
245       }
246     }
247 
248     @Override
249     public SortedSet<E> subSet(E fromElement, E toElement) {
250       synchronized (mutex) {
251         return sortedSet(delegate().subSet(fromElement, toElement), mutex);
252       }
253     }
254 
255     @Override
256     public SortedSet<E> headSet(E toElement) {
257       synchronized (mutex) {
258         return sortedSet(delegate().headSet(toElement), mutex);
259       }
260     }
261 
262     @Override
263     public SortedSet<E> tailSet(E fromElement) {
264       synchronized (mutex) {
265         return sortedSet(delegate().tailSet(fromElement), mutex);
266       }
267     }
268 
269     @Override
270     public E first() {
271       synchronized (mutex) {
272         return delegate().first();
273       }
274     }
275 
276     @Override
277     public E last() {
278       synchronized (mutex) {
279         return delegate().last();
280       }
281     }
282 
283     private static final long serialVersionUID = 0;
284   }
285 
286   private static <E> List<E> list(List<E> list, @Nullable Object mutex) {
287     return (list instanceof RandomAccess)
288         ? new SynchronizedRandomAccessList<E>(list, mutex)
289         : new SynchronizedList<E>(list, mutex);
290   }
291 
292   private static class SynchronizedList<E> extends SynchronizedCollection<E>
293       implements List<E> {
294     SynchronizedList(List<E> delegate, @Nullable Object mutex) {
295       super(delegate, mutex);
296     }
297 
298     @Override List<E> delegate() {
299       return (List<E>) super.delegate();
300     }
301 
302     @Override
303     public void add(int index, E element) {
304       synchronized (mutex) {
305         delegate().add(index, element);
306       }
307     }
308 
309     @Override
310     public boolean addAll(int index, Collection<? extends E> c) {
311       synchronized (mutex) {
312         return delegate().addAll(index, c);
313       }
314     }
315 
316     @Override
317     public E get(int index) {
318       synchronized (mutex) {
319         return delegate().get(index);
320       }
321     }
322 
323     @Override
324     public int indexOf(Object o) {
325       synchronized (mutex) {
326         return delegate().indexOf(o);
327       }
328     }
329 
330     @Override
331     public int lastIndexOf(Object o) {
332       synchronized (mutex) {
333         return delegate().lastIndexOf(o);
334       }
335     }
336 
337     @Override
338     public ListIterator<E> listIterator() {
339       return delegate().listIterator(); // manually synchronized
340     }
341 
342     @Override
343     public ListIterator<E> listIterator(int index) {
344       return delegate().listIterator(index); // manually synchronized
345     }
346 
347     @Override
348     public E remove(int index) {
349       synchronized (mutex) {
350         return delegate().remove(index);
351       }
352     }
353 
354     @Override
355     public E set(int index, E element) {
356       synchronized (mutex) {
357         return delegate().set(index, element);
358       }
359     }
360 
361     @Override
362     public List<E> subList(int fromIndex, int toIndex) {
363       synchronized (mutex) {
364         return list(delegate().subList(fromIndex, toIndex), mutex);
365       }
366     }
367 
368     @Override public boolean equals(Object o) {
369       if (o == this) {
370         return true;
371       }
372       synchronized (mutex) {
373         return delegate().equals(o);
374       }
375     }
376 
377     @Override public int hashCode() {
378       synchronized (mutex) {
379         return delegate().hashCode();
380       }
381     }
382 
383     private static final long serialVersionUID = 0;
384   }
385 
386   private static class SynchronizedRandomAccessList<E>
387       extends SynchronizedList<E> implements RandomAccess {
388     SynchronizedRandomAccessList(List<E> list, @Nullable Object mutex) {
389       super(list, mutex);
390     }
391     private static final long serialVersionUID = 0;
392   }
393 
394   static <E> Multiset<E> multiset(
395       Multiset<E> multiset, @Nullable Object mutex) {
396     if (multiset instanceof SynchronizedMultiset ||
397         multiset instanceof ImmutableMultiset) {
398       return multiset;
399     }
400     return new SynchronizedMultiset<E>(multiset, mutex);
401   }
402 
403   private static class SynchronizedMultiset<E> extends SynchronizedCollection<E>
404       implements Multiset<E> {
405     transient Set<E> elementSet;
406     transient Set<Entry<E>> entrySet;
407 
408     SynchronizedMultiset(Multiset<E> delegate, @Nullable Object mutex) {
409       super(delegate, mutex);
410     }
411 
412     @Override Multiset<E> delegate() {
413       return (Multiset<E>) super.delegate();
414     }
415 
416     @Override
417     public int count(Object o) {
418       synchronized (mutex) {
419         return delegate().count(o);
420       }
421     }
422 
423     @Override
424     public int add(E e, int n) {
425       synchronized (mutex) {
426         return delegate().add(e, n);
427       }
428     }
429 
430     @Override
431     public int remove(Object o, int n) {
432       synchronized (mutex) {
433         return delegate().remove(o, n);
434       }
435     }
436 
437     @Override
438     public int setCount(E element, int count) {
439       synchronized (mutex) {
440         return delegate().setCount(element, count);
441       }
442     }
443 
444     @Override
445     public boolean setCount(E element, int oldCount, int newCount) {
446       synchronized (mutex) {
447         return delegate().setCount(element, oldCount, newCount);
448       }
449     }
450 
451     @Override
452     public Set<E> elementSet() {
453       synchronized (mutex) {
454         if (elementSet == null) {
455           elementSet = typePreservingSet(delegate().elementSet(), mutex);
456         }
457         return elementSet;
458       }
459     }
460 
461     @Override
462     public Set<Entry<E>> entrySet() {
463       synchronized (mutex) {
464         if (entrySet == null) {
465           entrySet = typePreservingSet(delegate().entrySet(), mutex);
466         }
467         return entrySet;
468       }
469     }
470 
471     @Override public boolean equals(Object o) {
472       if (o == this) {
473         return true;
474       }
475       synchronized (mutex) {
476         return delegate().equals(o);
477       }
478     }
479 
480     @Override public int hashCode() {
481       synchronized (mutex) {
482         return delegate().hashCode();
483       }
484     }
485 
486     private static final long serialVersionUID = 0;
487   }
488 
489   static <K, V> Multimap<K, V> multimap(
490       Multimap<K, V> multimap, @Nullable Object mutex) {
491     if (multimap instanceof SynchronizedMultimap ||
492         multimap instanceof ImmutableMultimap) {
493       return multimap;
494     }
495     return new SynchronizedMultimap<K, V>(multimap, mutex);
496   }
497 
498   private static class SynchronizedMultimap<K, V> extends SynchronizedObject
499       implements Multimap<K, V> {
500     transient Set<K> keySet;
501     transient Collection<V> valuesCollection;
502     transient Collection<Map.Entry<K, V>> entries;
503     transient Map<K, Collection<V>> asMap;
504     transient Multiset<K> keys;
505 
506     @SuppressWarnings("unchecked")
507     @Override Multimap<K, V> delegate() {
508       return (Multimap<K, V>) super.delegate();
509     }
510 
511     SynchronizedMultimap(Multimap<K, V> delegate, @Nullable Object mutex) {
512       super(delegate, mutex);
513     }
514 
515     @Override
516     public int size() {
517       synchronized (mutex) {
518         return delegate().size();
519       }
520     }
521 
522     @Override
523     public boolean isEmpty() {
524       synchronized (mutex) {
525         return delegate().isEmpty();
526       }
527     }
528 
529     @Override
530     public boolean containsKey(Object key) {
531       synchronized (mutex) {
532         return delegate().containsKey(key);
533       }
534     }
535 
536     @Override
537     public boolean containsValue(Object value) {
538       synchronized (mutex) {
539         return delegate().containsValue(value);
540       }
541     }
542 
543     @Override
544     public boolean containsEntry(Object key, Object value) {
545       synchronized (mutex) {
546         return delegate().containsEntry(key, value);
547       }
548     }
549 
550     @Override
551     public Collection<V> get(K key) {
552       synchronized (mutex) {
553         return typePreservingCollection(delegate().get(key), mutex);
554       }
555     }
556 
557     @Override
558     public boolean put(K key, V value) {
559       synchronized (mutex) {
560         return delegate().put(key, value);
561       }
562     }
563 
564     @Override
565     public boolean putAll(K key, Iterable<? extends V> values) {
566       synchronized (mutex) {
567         return delegate().putAll(key, values);
568       }
569     }
570 
571     @Override
572     public boolean putAll(Multimap<? extends K, ? extends V> multimap) {
573       synchronized (mutex) {
574         return delegate().putAll(multimap);
575       }
576     }
577 
578     @Override
579     public Collection<V> replaceValues(K key, Iterable<? extends V> values) {
580       synchronized (mutex) {
581         return delegate().replaceValues(key, values); // copy not synchronized
582       }
583     }
584 
585     @Override
586     public boolean remove(Object key, Object value) {
587       synchronized (mutex) {
588         return delegate().remove(key, value);
589       }
590     }
591 
592     @Override
593     public Collection<V> removeAll(Object key) {
594       synchronized (mutex) {
595         return delegate().removeAll(key); // copy not synchronized
596       }
597     }
598 
599     @Override
600     public void clear() {
601       synchronized (mutex) {
602         delegate().clear();
603       }
604     }
605 
606     @Override
607     public Set<K> keySet() {
608       synchronized (mutex) {
609         if (keySet == null) {
610           keySet = typePreservingSet(delegate().keySet(), mutex);
611         }
612         return keySet;
613       }
614     }
615 
616     @Override
617     public Collection<V> values() {
618       synchronized (mutex) {
619         if (valuesCollection == null) {
620           valuesCollection = collection(delegate().values(), mutex);
621         }
622         return valuesCollection;
623       }
624     }
625 
626     @Override
627     public Collection<Map.Entry<K, V>> entries() {
628       synchronized (mutex) {
629         if (entries == null) {
630           entries = typePreservingCollection(delegate().entries(), mutex);
631         }
632         return entries;
633       }
634     }
635 
636     @Override
637     public Map<K, Collection<V>> asMap() {
638       synchronized (mutex) {
639         if (asMap == null) {
640           asMap = new SynchronizedAsMap<K, V>(delegate().asMap(), mutex);
641         }
642         return asMap;
643       }
644     }
645 
646     @Override
647     public Multiset<K> keys() {
648       synchronized (mutex) {
649         if (keys == null) {
650           keys = multiset(delegate().keys(), mutex);
651         }
652         return keys;
653       }
654     }
655 
656     @Override public boolean equals(Object o) {
657       if (o == this) {
658         return true;
659       }
660       synchronized (mutex) {
661         return delegate().equals(o);
662       }
663     }
664 
665     @Override public int hashCode() {
666       synchronized (mutex) {
667         return delegate().hashCode();
668       }
669     }
670 
671     private static final long serialVersionUID = 0;
672   }
673 
674   static <K, V> ListMultimap<K, V> listMultimap(
675       ListMultimap<K, V> multimap, @Nullable Object mutex) {
676     if (multimap instanceof SynchronizedListMultimap ||
677         multimap instanceof ImmutableListMultimap) {
678       return multimap;
679     }
680     return new SynchronizedListMultimap<K, V>(multimap, mutex);
681   }
682 
683   private static class SynchronizedListMultimap<K, V>
684       extends SynchronizedMultimap<K, V> implements ListMultimap<K, V> {
685     SynchronizedListMultimap(
686         ListMultimap<K, V> delegate, @Nullable Object mutex) {
687       super(delegate, mutex);
688     }
689     @Override ListMultimap<K, V> delegate() {
690       return (ListMultimap<K, V>) super.delegate();
691     }
692     @Override public List<V> get(K key) {
693       synchronized (mutex) {
694         return list(delegate().get(key), mutex);
695       }
696     }
697     @Override public List<V> removeAll(Object key) {
698       synchronized (mutex) {
699         return delegate().removeAll(key); // copy not synchronized
700       }
701     }
702     @Override public List<V> replaceValues(
703         K key, Iterable<? extends V> values) {
704       synchronized (mutex) {
705         return delegate().replaceValues(key, values); // copy not synchronized
706       }
707     }
708     private static final long serialVersionUID = 0;
709   }
710 
711   static <K, V> SetMultimap<K, V> setMultimap(
712       SetMultimap<K, V> multimap, @Nullable Object mutex) {
713     if (multimap instanceof SynchronizedSetMultimap ||
714         multimap instanceof ImmutableSetMultimap) {
715       return multimap;
716     }
717     return new SynchronizedSetMultimap<K, V>(multimap, mutex);
718   }
719 
720   private static class SynchronizedSetMultimap<K, V>
721       extends SynchronizedMultimap<K, V> implements SetMultimap<K, V> {
722     transient Set<Map.Entry<K, V>> entrySet;
723 
724     SynchronizedSetMultimap(
725         SetMultimap<K, V> delegate, @Nullable Object mutex) {
726       super(delegate, mutex);
727     }
728     @Override SetMultimap<K, V> delegate() {
729       return (SetMultimap<K, V>) super.delegate();
730     }
731     @Override public Set<V> get(K key) {
732       synchronized (mutex) {
733         return set(delegate().get(key), mutex);
734       }
735     }
736     @Override public Set<V> removeAll(Object key) {
737       synchronized (mutex) {
738         return delegate().removeAll(key); // copy not synchronized
739       }
740     }
741     @Override public Set<V> replaceValues(
742         K key, Iterable<? extends V> values) {
743       synchronized (mutex) {
744         return delegate().replaceValues(key, values); // copy not synchronized
745       }
746     }
747     @Override public Set<Map.Entry<K, V>> entries() {
748       synchronized (mutex) {
749         if (entrySet == null) {
750           entrySet = set(delegate().entries(), mutex);
751         }
752         return entrySet;
753       }
754     }
755     private static final long serialVersionUID = 0;
756   }
757 
758   static <K, V> SortedSetMultimap<K, V> sortedSetMultimap(
759       SortedSetMultimap<K, V> multimap, @Nullable Object mutex) {
760     if (multimap instanceof SynchronizedSortedSetMultimap) {
761       return multimap;
762     }
763     return new SynchronizedSortedSetMultimap<K, V>(multimap, mutex);
764   }
765 
766   private static class SynchronizedSortedSetMultimap<K, V>
767       extends SynchronizedSetMultimap<K, V> implements SortedSetMultimap<K, V> {
768     SynchronizedSortedSetMultimap(
769         SortedSetMultimap<K, V> delegate, @Nullable Object mutex) {
770       super(delegate, mutex);
771     }
772     @Override SortedSetMultimap<K, V> delegate() {
773       return (SortedSetMultimap<K, V>) super.delegate();
774     }
775     @Override public SortedSet<V> get(K key) {
776       synchronized (mutex) {
777         return sortedSet(delegate().get(key), mutex);
778       }
779     }
780     @Override public SortedSet<V> removeAll(Object key) {
781       synchronized (mutex) {
782         return delegate().removeAll(key); // copy not synchronized
783       }
784     }
785     @Override public SortedSet<V> replaceValues(
786         K key, Iterable<? extends V> values) {
787       synchronized (mutex) {
788         return delegate().replaceValues(key, values); // copy not synchronized
789       }
790     }
791     @Override
792     public Comparator<? super V> valueComparator() {
793       synchronized (mutex) {
794         return delegate().valueComparator();
795       }
796     }
797     private static final long serialVersionUID = 0;
798   }
799 
800   private static <E> Collection<E> typePreservingCollection(
801       Collection<E> collection, @Nullable Object mutex) {
802     if (collection instanceof SortedSet) {
803       return sortedSet((SortedSet<E>) collection, mutex);
804     }
805     if (collection instanceof Set) {
806       return set((Set<E>) collection, mutex);
807     }
808     if (collection instanceof List) {
809       return list((List<E>) collection, mutex);
810     }
811     return collection(collection, mutex);
812   }
813 
814   private static <E> Set<E> typePreservingSet(
815       Set<E> set, @Nullable Object mutex) {
816     if (set instanceof SortedSet) {
817       return sortedSet((SortedSet<E>) set, mutex);
818     } else {
819       return set(set, mutex);
820     }
821   }
822 
823   private static class SynchronizedAsMapEntries<K, V>
824       extends SynchronizedSet<Map.Entry<K, Collection<V>>> {
825     SynchronizedAsMapEntries(
826         Set<Map.Entry<K, Collection<V>>> delegate, @Nullable Object mutex) {
827       super(delegate, mutex);
828     }
829 
830     @Override public Iterator<Map.Entry<K, Collection<V>>> iterator() {
831       // Must be manually synchronized.
832       final Iterator<Map.Entry<K, Collection<V>>> iterator = super.iterator();
833       return new ForwardingIterator<Map.Entry<K, Collection<V>>>() {
834         @Override protected Iterator<Map.Entry<K, Collection<V>>> delegate() {
835           return iterator;
836         }
837 
838         @Override public Map.Entry<K, Collection<V>> next() {
839           final Map.Entry<K, Collection<V>> entry = super.next();
840           return new ForwardingMapEntry<K, Collection<V>>() {
841             @Override protected Map.Entry<K, Collection<V>> delegate() {
842               return entry;
843             }
844             @Override public Collection<V> getValue() {
845               return typePreservingCollection(entry.getValue(), mutex);
846             }
847           };
848         }
849       };
850     }
851 
852     // See Collections.CheckedMap.CheckedEntrySet for details on attacks.
853 
854     @Override public Object[] toArray() {
855       synchronized (mutex) {
856         return ObjectArrays.toArrayImpl(delegate());
857       }
858     }
859     @Override public <T> T[] toArray(T[] array) {
860       synchronized (mutex) {
861         return ObjectArrays.toArrayImpl(delegate(), array);
862       }
863     }
864     @Override public boolean contains(Object o) {
865       synchronized (mutex) {
866         return Maps.containsEntryImpl(delegate(), o);
867       }
868     }
869     @Override public boolean containsAll(Collection<?> c) {
870       synchronized (mutex) {
871         return Collections2.containsAllImpl(delegate(), c);
872       }
873     }
874     @Override public boolean equals(Object o) {
875       if (o == this) {
876         return true;
877       }
878       synchronized (mutex) {
879         return Sets.equalsImpl(delegate(), o);
880       }
881     }
882     @Override public boolean remove(Object o) {
883       synchronized (mutex) {
884         return Maps.removeEntryImpl(delegate(), o);
885       }
886     }
887     @Override public boolean removeAll(Collection<?> c) {
888       synchronized (mutex) {
889         return Iterators.removeAll(delegate().iterator(), c);
890       }
891     }
892     @Override public boolean retainAll(Collection<?> c) {
893       synchronized (mutex) {
894         return Iterators.retainAll(delegate().iterator(), c);
895       }
896     }
897 
898     private static final long serialVersionUID = 0;
899   }
900 
901   @VisibleForTesting
902   static <K, V> Map<K, V> map(Map<K, V> map, @Nullable Object mutex) {
903     return new SynchronizedMap<K, V>(map, mutex);
904   }
905 
906   private static class SynchronizedMap<K, V> extends SynchronizedObject
907       implements Map<K, V> {
908     transient Set<K> keySet;
909     transient Collection<V> values;
910     transient Set<Map.Entry<K, V>> entrySet;
911 
912     SynchronizedMap(Map<K, V> delegate, @Nullable Object mutex) {
913       super(delegate, mutex);
914     }
915 
916     @SuppressWarnings("unchecked")
917     @Override Map<K, V> delegate() {
918       return (Map<K, V>) super.delegate();
919     }
920 
921     @Override
922     public void clear() {
923       synchronized (mutex) {
924         delegate().clear();
925       }
926     }
927 
928     @Override
929     public boolean containsKey(Object key) {
930       synchronized (mutex) {
931         return delegate().containsKey(key);
932       }
933     }
934 
935     @Override
936     public boolean containsValue(Object value) {
937       synchronized (mutex) {
938         return delegate().containsValue(value);
939       }
940     }
941 
942     @Override
943     public Set<Map.Entry<K, V>> entrySet() {
944       synchronized (mutex) {
945         if (entrySet == null) {
946           entrySet = set(delegate().entrySet(), mutex);
947         }
948         return entrySet;
949       }
950     }
951 
952     @Override
953     public V get(Object key) {
954       synchronized (mutex) {
955         return delegate().get(key);
956       }
957     }
958 
959     @Override
960     public boolean isEmpty() {
961       synchronized (mutex) {
962         return delegate().isEmpty();
963       }
964     }
965 
966     @Override
967     public Set<K> keySet() {
968       synchronized (mutex) {
969         if (keySet == null) {
970           keySet = set(delegate().keySet(), mutex);
971         }
972         return keySet;
973       }
974     }
975 
976     @Override
977     public V put(K key, V value) {
978       synchronized (mutex) {
979         return delegate().put(key, value);
980       }
981     }
982 
983     @Override
984     public void putAll(Map<? extends K, ? extends V> map) {
985       synchronized (mutex) {
986         delegate().putAll(map);
987       }
988     }
989 
990     @Override
991     public V remove(Object key) {
992       synchronized (mutex) {
993         return delegate().remove(key);
994       }
995     }
996 
997     @Override
998     public int size() {
999       synchronized (mutex) {
1000         return delegate().size();
1001       }
1002     }
1003 
1004     @Override
1005     public Collection<V> values() {
1006       synchronized (mutex) {
1007         if (values == null) {
1008           values = collection(delegate().values(), mutex);
1009         }
1010         return values;
1011       }
1012     }
1013 
1014     @Override public boolean equals(Object o) {
1015       if (o == this) {
1016         return true;
1017       }
1018       synchronized (mutex) {
1019         return delegate().equals(o);
1020       }
1021     }
1022 
1023     @Override public int hashCode() {
1024       synchronized (mutex) {
1025         return delegate().hashCode();
1026       }
1027     }
1028 
1029     private static final long serialVersionUID = 0;
1030   }
1031 
1032   static <K, V> SortedMap<K, V> sortedMap(
1033       SortedMap<K, V> sortedMap, @Nullable Object mutex) {
1034     return new SynchronizedSortedMap<K, V>(sortedMap, mutex);
1035   }
1036 
1037   static class SynchronizedSortedMap<K, V> extends SynchronizedMap<K, V>
1038       implements SortedMap<K, V> {
1039 
1040     SynchronizedSortedMap(SortedMap<K, V> delegate, @Nullable Object mutex) {
1041       super(delegate, mutex);
1042     }
1043 
1044     @Override SortedMap<K, V> delegate() {
1045       return (SortedMap<K, V>) super.delegate();
1046     }
1047 
1048     @Override public Comparator<? super K> comparator() {
1049       synchronized (mutex) {
1050         return delegate().comparator();
1051       }
1052     }
1053 
1054     @Override public K firstKey() {
1055       synchronized (mutex) {
1056         return delegate().firstKey();
1057       }
1058     }
1059 
1060     @Override public SortedMap<K, V> headMap(K toKey) {
1061       synchronized (mutex) {
1062         return sortedMap(delegate().headMap(toKey), mutex);
1063       }
1064     }
1065 
1066     @Override public K lastKey() {
1067       synchronized (mutex) {
1068         return delegate().lastKey();
1069       }
1070     }
1071 
1072     @Override public SortedMap<K, V> subMap(K fromKey, K toKey) {
1073       synchronized (mutex) {
1074         return sortedMap(delegate().subMap(fromKey, toKey), mutex);
1075       }
1076     }
1077 
1078     @Override public SortedMap<K, V> tailMap(K fromKey) {
1079       synchronized (mutex) {
1080         return sortedMap(delegate().tailMap(fromKey), mutex);
1081       }
1082     }
1083 
1084     private static final long serialVersionUID = 0;
1085   }
1086 
1087   static <K, V> BiMap<K, V> biMap(BiMap<K, V> bimap, @Nullable Object mutex) {
1088     if (bimap instanceof SynchronizedBiMap ||
1089         bimap instanceof ImmutableBiMap) {
1090       return bimap;
1091     }
1092     return new SynchronizedBiMap<K, V>(bimap, mutex, null);
1093   }
1094 
1095   @VisibleForTesting static class SynchronizedBiMap<K, V>
1096       extends SynchronizedMap<K, V> implements BiMap<K, V>, Serializable {
1097     private transient Set<V> valueSet;
1098     private transient BiMap<V, K> inverse;
1099 
1100     private SynchronizedBiMap(BiMap<K, V> delegate, @Nullable Object mutex,
1101         @Nullable BiMap<V, K> inverse) {
1102       super(delegate, mutex);
1103       this.inverse = inverse;
1104     }
1105 
1106     @Override BiMap<K, V> delegate() {
1107       return (BiMap<K, V>) super.delegate();
1108     }
1109 
1110     @Override public Set<V> values() {
1111       synchronized (mutex) {
1112         if (valueSet == null) {
1113           valueSet = set(delegate().values(), mutex);
1114         }
1115         return valueSet;
1116       }
1117     }
1118 
1119     @Override
1120     public V forcePut(K key, V value) {
1121       synchronized (mutex) {
1122         return delegate().forcePut(key, value);
1123       }
1124     }
1125 
1126     @Override
1127     public BiMap<V, K> inverse() {
1128       synchronized (mutex) {
1129         if (inverse == null) {
1130           inverse
1131               = new SynchronizedBiMap<V, K>(delegate().inverse(), mutex, this);
1132         }
1133         return inverse;
1134       }
1135     }
1136 
1137     private static final long serialVersionUID = 0;
1138   }
1139 
1140   private static class SynchronizedAsMap<K, V>
1141       extends SynchronizedMap<K, Collection<V>> {
1142     transient Set<Map.Entry<K, Collection<V>>> asMapEntrySet;
1143     transient Collection<Collection<V>> asMapValues;
1144 
1145     SynchronizedAsMap(Map<K, Collection<V>> delegate, @Nullable Object mutex) {
1146       super(delegate, mutex);
1147     }
1148 
1149     @Override public Collection<V> get(Object key) {
1150       synchronized (mutex) {
1151         Collection<V> collection = super.get(key);
1152         return (collection == null) ? null
1153             : typePreservingCollection(collection, mutex);
1154       }
1155     }
1156 
1157     @Override public Set<Map.Entry<K, Collection<V>>> entrySet() {
1158       synchronized (mutex) {
1159         if (asMapEntrySet == null) {
1160           asMapEntrySet = new SynchronizedAsMapEntries<K, V>(
1161               delegate().entrySet(), mutex);
1162         }
1163         return asMapEntrySet;
1164       }
1165     }
1166 
1167     @Override public Collection<Collection<V>> values() {
1168       synchronized (mutex) {
1169         if (asMapValues == null) {
1170           asMapValues
1171               = new SynchronizedAsMapValues<V>(delegate().values(), mutex);
1172         }
1173         return asMapValues;
1174       }
1175     }
1176 
1177     @Override public boolean containsValue(Object o) {
1178       // values() and its contains() method are both synchronized.
1179       return values().contains(o);
1180     }
1181 
1182     private static final long serialVersionUID = 0;
1183   }
1184 
1185   private static class SynchronizedAsMapValues<V>
1186       extends SynchronizedCollection<Collection<V>> {
1187     SynchronizedAsMapValues(
1188         Collection<Collection<V>> delegate, @Nullable Object mutex) {
1189       super(delegate, mutex);
1190     }
1191 
1192     @Override public Iterator<Collection<V>> iterator() {
1193       // Must be manually synchronized.
1194       final Iterator<Collection<V>> iterator = super.iterator();
1195       return new ForwardingIterator<Collection<V>>() {
1196         @Override protected Iterator<Collection<V>> delegate() {
1197           return iterator;
1198         }
1199         @Override public Collection<V> next() {
1200           return typePreservingCollection(super.next(), mutex);
1201         }
1202       };
1203     }
1204 
1205     private static final long serialVersionUID = 0;
1206   }
1207 
1208   static <E> Queue<E> queue(Queue<E> queue, @Nullable Object mutex) {
1209     return (queue instanceof SynchronizedQueue)
1210         ? queue
1211         : new SynchronizedQueue<E>(queue, mutex);
1212   }
1213 
1214   private static class SynchronizedQueue<E> extends SynchronizedCollection<E>
1215       implements Queue<E> {
1216 
1217     SynchronizedQueue(Queue<E> delegate, @Nullable Object mutex) {
1218       super(delegate, mutex);
1219     }
1220 
1221     @Override Queue<E> delegate() {
1222       return (Queue<E>) super.delegate();
1223     }
1224 
1225     @Override
1226     public E element() {
1227       synchronized (mutex) {
1228         return delegate().element();
1229       }
1230     }
1231 
1232     @Override
1233     public boolean offer(E e) {
1234       synchronized (mutex) {
1235         return delegate().offer(e);
1236       }
1237     }
1238 
1239     @Override
1240     public E peek() {
1241       synchronized (mutex) {
1242         return delegate().peek();
1243       }
1244     }
1245 
1246     @Override
1247     public E poll() {
1248       synchronized (mutex) {
1249         return delegate().poll();
1250       }
1251     }
1252 
1253     @Override
1254     public E remove() {
1255       synchronized (mutex) {
1256         return delegate().remove();
1257       }
1258     }
1259 
1260     private static final long serialVersionUID = 0;
1261   }
1262 }
1263